A digital signature is a value s that can be calculated only when a signer who knows a secret key sk corresponding to a public key pk uses the secret key sk correctly for a message M, and the value is used as an electronic signature. Any party can verify the validity of the correctly calculated signature by using the public key pk, and any third parties that do not know the secret key sk cannot obtain the valid signature s.
The digital signature is used as a basic element in a variety of encryption protocols used for electronic money, credentials systems, and the like. In particular, advanced uses are frequently found among applications that require private information of the user. For example, in combination with zero-knowledge proofs, if elements (public key pk, signature s, message M) of a signature are true ones that satisfy a verification equation, any third party is convinced of the fact with some or all of the elements kept secret.
Recent progress in pairing technology has enabled zero-knowledge proofs (Jens Groth and Amit Sahai, “Efficient Non-interactive Proof Systems for Bilinear Groups,” Eurocrypt 2008, LNCS 2965, pp. 415-432) that efficiently prove the fact that elements of a group satisfy an equality defined as a product of bilinear mapping. Accordingly, if all the elements of a signature are group elements and if the signature verification equation is a product of bilinear mapping, the corresponding signature system can easily keep any element of the signature secret. The signature system in which all the elements of a signature are group elements and the signature verification equation is a product of bilinear mapping is referred to as a group structure preserving signature system.
Known conventional technologies of group structure preserving signature systems include the technologies in Non-patent literatures 1 to 4. The technology in Non-patent literature 1 is referred to as a CL-Signature method. This method, however, uses idealized impractical elements, which are referred to as random oracles, and its security in practical implementations is unclear.
The system in Non-patent literature 2 is an improved CL-Signature method which does not use random oracles. This method, however, ensures security only with respect to a message selected at random, and security from chosen message attacks, which is generally demanded as the security of signatures, is unclear.
Non-patent literature 3 describes a method that is guaranteed to be resistant to chosen message attacks. In this method, a signature consists of seven group elements σ=(z, r, s, t, u, v, w) that satisfy the two verification equations given below.e(a1,ã1)e(a2,ã2)=e(gz,z)e(gr,r)e(s,t)Πi=1ke(gi,mi),e(b1,{tilde over (b)}1)e(b2,{tilde over (b)}2)=e(hz,z)e(hu,u)e(v,w)Πi=1ke(hi,mi)
All the elements in the verification equations that are not included in σ are public keys.
The system in non-patent literature 4 allows a signature to be composed of a smaller number of group elements than the system in Non-patent literature 3. This method, however, provides security only in groups based on asymmetric bilinear mapping, and there is specific attack in groups based on symmetric bilinear mapping, which is used often in encryption protocols.